10880. Колин и Район

У Колина и Района праздник. Они приготовили c пирожных и пригласили g гостей. Каждый гость съел q пирожных, при этом еще r (r < q) пирожных осталось.

Вход. Первая строка содержит количество тестов n. Каждая строка содержит значения c и r (c, r £ 2*10⁹).

Выход. Для каждого теста вывести его номер и число пирожных q, которое съел каждый гость. Если таких чисел несколько, то вывести все их в возрастающем порядке. Числа разделять одним пробелом, в конце каждой строки не должно быть лишних пробелов. Если c = r, то выводить 0.

Пример входа

4

10 0

13 2

300 98

1000 997

Пример выхода

Case #1: 1 2 5 10

Case #2: 11

Case #3: 101 202

Case #4:

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Согласно условию задачи имеет место равенство: c = g * q + r, r < q. Поскольку известны c и r, то известно значение g * q. Ответом задачи будут все делители числа g * q = c – r, большие r и отсортированные по возрастанию.

Пример

Во втором тесте g * q = c – r = 13 – 2 = 11. Делителями числа 11 будут 1 и 11, но только 11 больше r = 2.

Реализация алгоритма

Читаем количество тестов t. Для каждого теста вводим значения c и r.

scanf("%d",&t);

for(i = 1; i <= t; i++)

{

scanf("%d %d",&c, &r);

Положим c = g * q = c – r. Если c = 0, то выводим 0 и переходим к следующему тесту.

c = c - r;

if (!c) {printf("Case #%d: 0\n",i); continue;}

Очищаем вектор v, в него будем складывать всевозможные делители числа c = g * q. Для этого перебираем все числа j от 1 до up = . Если j – делитель, то заносим в вектор v делители j и c / j.

v.clear(); up = int(sqrt(1.0*c));

for(j = 1; j <= up; j++)

if (c % j == 0)

{

if (j > r) v.push_back(j);

if (c / j > r) v.push_back(c / j);

}

Если значение c является полным квадратом и up > r, то в вектор v будут занесены два равных делителя: up и c / up = up. Оба эти значения находится в конце вектора, удалим последний элемент.

if ((c == up * up) && (up > r)) v.pop_back();

Сортируем найденные делители.

sort(v.begin(),v.end());

Выводим номер теста и все возможные значения q в возрастающем порядке.

printf("Case #%d:",i);

for(j = 0; j < v.size(); j++) printf(" %d",v[j]);

printf("\n");

}